home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / GW AdaEd 1.4.2 / GWAdaDemos / NYUDemos / PRIMES3.ADA < prev    next >
Text File  |  1993-01-31  |  3KB  |  85 lines
  1. -- A pipeline version of the Sieve or Erastosthenes: we create a chain of tasks
  2. -- each of which holds several primes. The main program feeds successive integers
  3. -- into the pipe; each task tests the integer for divisibility by its own
  4. -- primes, and passes it along to the next task if not divisible. Each task has
  5. -- a pointer to its successor. The end of the pipeline creates a new task when
  6. -- a new prime is discovered and its own complement of primes is full.
  7. -- The value of max regulates the coarseness of the parallel computation.
  8.  
  9. package prime_dividers is
  10.    type int is range 1..1000000 ;        -- for primes up to 10**6
  11.    task type divider is
  12.        entry my_first(x: int);            -- To initialize the task.
  13.        entry maybe_prime(x: int) ;        -- for successive tests.
  14.    end divider;
  15. end prime_dividers ;
  16.  
  17. with text_io; use text_io;
  18. package body prime_dividers is
  19.    type pointer is access divider ;        -- who's next.
  20.  
  21.    procedure initialize(ptr: in out pointer; value: int) is
  22.    begin
  23.       ptr := new divider ;
  24.       ptr.my_first(value) ;
  25.    end initialize; 
  26.  
  27.    task body divider is
  28.      max: constant := 10;            -- number of primes per task.
  29.      subtype cap is integer range 1..max;
  30.      my_primes: array(cap) of int ;
  31.      last: cap := 1;
  32.      is_prime: boolean := false ;
  33.      next: pointer ;
  34.      candidate: int ;
  35.    begin
  36.     accept my_first(x:int) do 
  37.         my_primes(last) := x ;             -- now we know.
  38.             put_line("new task with prime: "& int'image(x)) ;
  39.         end ;
  40.         loop
  41.          select
  42.            accept maybe_prime(x: int) do 
  43.            candidate := x; 
  44.            is_prime := true ;              -- maybe.
  45.            for i in 1..last loop
  46.                    if candidate mod my_primes(i) = 0 then -- not a prime.
  47.             is_prime := false ;
  48.             exit ;    
  49.                elsif my_primes(i)**2 > candidate then 
  50.             exit ;                -- must be prime.
  51.            end if ;
  52.                end loop  ;
  53.             end maybe_prime ;
  54.             if is_prime then
  55.                  if last < max then            -- keep locally.
  56.             last := last +1 ;
  57.             my_primes(last) := candidate ;
  58.                     put_line("new prime: "& int'image(candidate)) ;
  59.              elsif next = null then            -- need new task.
  60.                   initialize(next, candidate) ;         
  61.               else
  62.                   next.maybe_prime(candidate) ;    -- needs further test.
  63.                  end if ; 
  64.          end if ;
  65.          or
  66.          terminate ;
  67.          end select ;
  68.          end loop;
  69.     end divider;
  70. end prime_dividers;
  71.     
  72. with prime_dividers; use prime_dividers ;
  73. with text_io; use text_io;
  74. procedure main is
  75.    first_prime: divider ;            -- Beginning of pipeline.
  76. begin
  77.     first_prime.my_first(3) ;        -- No need to test even numbers
  78.     for i in int range 2..2000 loop
  79.         first_prime.maybe_prime(2*i+1) ;
  80.     end loop;
  81. end main ;
  82.  
  83.  
  84.  
  85.